www.gusucode.com > C++ 各种排序算法演示(插入、希尔、冒泡、快速等)-源码程序 > C++ 各种排序算法演示(插入、希尔、冒泡、快速等)-源码程序/code/InsertSort/main.cpp

    //Download by http://www.NewXing.com
#include<iostream>
#include<ctime>
using namespace std;

//数组的第一个元素就不参与到排序中，即测试数据的第一个记录不参与排序
//为数组的第一个元素r[0]留作他用

//直接插入排序
void InsertSort(int r[],int n)
{
	int i,j;
	int compare(0),move(0);
	for(i=2;i<n;++i)
	{
		compare++;
		if(r[i]<r[i-1])
		{
			r[0]=r[i];//哨兵
			for(j=i-1;r[0]<r[j];--j)//找插入位置
			{
				r[j+1]=r[j];//记录后移
				move++;//移动次数
			}
			r[j+1]=r[0];
		}
	}
	cout<<"比较次数："<<compare<<endl;
	cout<<"移动次数："<<move<<endl;
}

void main()
{
	int i;

	cout<<"直接插入排序测试:"<<endl;
	cout<<endl;
	
	cout<<"测试数据为正序："<<endl;
	int array1[10]={2,4,6,8,10,12,14,16,18,20};
	cout<<"排序前："<<endl;
	for(i=0;i<10;i++)
		cout<<array1[i]<<' ';
	cout<<endl;
	InsertSort(array1,10);
	cout<<"排序后："<<endl;
	for(i=0;i<10;i++)
		cout<<array1[i]<<' ';
	cout<<endl;
	cout<<endl;

	cout<<"测试数据为逆序："<<endl;
	int array2[11]={0,10,9,8,7,6,5,4,3,2,1};
	cout<<"排序前："<<endl;
	for(i=1;i<11;i++)//array2[0]=0不参与
		cout<<array2[i]<<' ';
	cout<<endl;
	InsertSort(array2,11);
	cout<<"排序后："<<endl;
	for(i=1;i<11;i++)//array2[0]=0不参与
		cout<<array2[i]<<' ';
	cout<<endl;
	cout<<endl;

	cout<<"测试数据为随机数据："<<endl;
	srand((unsigned)time(NULL));
	int random[11];
	random[0]=0;//random[0]=0不参与
	for(i=1;i<11;i++)
		random[i]=rand()%20;
	cout<<"排序前："<<endl;
	for(i=1;i<11;i++)
		cout<<random[i]<<' ';
	cout<<endl;
	InsertSort(random,11);
	cout<<"排序后："<<endl;
	for(i=1;i<11;i++)
		cout<<random[i]<<' ';
	cout<<endl;
	cout<<endl;

	cout<<"直接插入排序测试结束。"<<endl;
}